package pers.tz.题目.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author irony
 * @date 2024-03-11
 */
public class leetcode_0022_括号生成 {
//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//
// 示例 1：
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
//
// 示例 2：
//输入：n = 1
//输出：["()"]
//
// 提示：
// 1 <= n <= 8

    public static void main(String[] args) {
        System.out.println(generateParenthesis(5));
    }

    public static List<String> generateParenthesis(int n) {
        // 存放决定，左括号+右括号
        char[] path = new char[n << 1];
        List<String> ans = new ArrayList<>();
        // 回溯
        process(path, 0, 0, n, ans);
        return ans;
    }

    /**
     * 回溯计算
     *
     * @param path 做的决定，左括号还是右括号，path[0...index - 1]已经做完决定
     * @param index 当前做决定的位置
     * @param leftMinusRight 左括号减右括号的数量，用于剪枝
     * @param leftRest 剩余左括号的数量
     * @param ans 结果
     */
    private static void process(char[] path, int index, int leftMinusRight, int leftRest, List<String> ans) {
        // 如果所有决定都做完了
        if (path.length == index) {
            ans.add(String.valueOf(path));
        } else {
            // 做决定，即在index位置上放左括号还是右括号
            if (leftRest > 0) {
                path[index] = '(';
                // 深度优先遍历
                process(path, index + 1, leftMinusRight + 1, leftRest - 1, ans);
            }
            if (leftMinusRight > 0) {
                path[index] = ')';
                process(path, index + 1, leftMinusRight - 1, leftRest, ans);
            }
        }
    }
}
